The present invention relates generally to computer networks, and more specifically, to a method and apparatus for disseminating virtual local area network membership information across computer networks running multiple spanning trees.
A computer network typically comprises a plurality of interconnected entities. An entity may consist of any network device, such as a server or end station, that xe2x80x9csourcesxe2x80x9d (i.e., transmits) or xe2x80x9csinksxe2x80x9d (i.e., receives) data frames. A common type of computer network is a local area network (xe2x80x9cLANxe2x80x9d) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack). In many instances, several LANs are interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network (xe2x80x9cWANxe2x80x9d) or intranet that may span an entire country or continent.
One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a xe2x80x9cbridgingxe2x80x9d function between two or more LANs. Alternatively, a switch may be utilized to provide a xe2x80x9cswitchingxe2x80x9d function for transferring information between a plurality of LANs or end stations. Typically, the bridge or switch is a computer and includes a plurality of ports that are coupled to the LANs or end stations. Ports used to couple switches to each other are generally referred to as, a trunk ports, whereas ports used to couple switches to LANs or end stations are generally referred to as access ports. The switching function includes receiving data from a sending entity at a source port and transferring that data to at least one destination port for forwarding to a receiving entity.
Switches and bridges typically learn which destination port to use in order to reach a particular entity by noting on which source port the last message originating from that entity was received. This information is then stored in a block of memory referred to as a filtering database. Thereafter, when a message addressed to a given entity is received on a source port, the bridge looks up the entity in its filtering database and identifies the appropriate destination port to reach that entity. If no destination port is identified in the filtering database, the bridge floods the message out all ports, except the port on which the message was received. Messages addressed to broadcast or multicast addresses are also flooded.
Additionally, most computer networks include redundant communications paths so that a failure of any given link or device does not isolate any portion of the network. The existence of redundant links, however, may cause the formation of circuitous paths or xe2x80x9cloopsxe2x80x9d within the network. Loops are highly undesirable because data frames may traverse the loops indefinitely. Furthermore, because switches and bridges replicate (i.e., flood) frames whose destination port is unknown or which are directed to broadcast or multicast addresses, the existence of loops may cause a proliferation of data frames that effectively overwhelms the network.
Spanning Tree Algorithm
To avoid the formation of loops, many intermediate network devices execute a spanning tree algorithm that allows them to calculate an active network topology which is loop-free (i.e., a tree) and yet connects every pair of LANs within the network (i.e., the tree is spanning). The Institute of Electrical and Electronics Engineers (IEEE) has promulgated a standard (the 802.1D standard) that defines a spanning tree protocol to be executed by 802.1D compatible devices. In general, by executing the spanning tree protocol, bridges elect a single bridge to be the xe2x80x9crootxe2x80x9d bridge. In addition, for each LAN coupled to more than one bridge, only one (the xe2x80x9cdesignated bridgexe2x80x9d) is elected to forward frames to and from the respective LAN. The designated bridge is typically the one closest to the root. Each bridge also selects one port (its xe2x80x9croot portxe2x80x9d) which gives the lowest cost path to the root.
The root ports and designated bridge ports are selected for inclusion in the active topology and are placed in a forwarding state so that data frames may be forwarded to and from these ports and thus onto the corresponding paths or links of the network. Ports not included within the active topology are placed in a blocking state. When a port is in the blocking state, data frames are not forwarded to or received from the port. A network administrator may also exclude a port from the spanning tree by placing it in a disabled state.
To obtain the information necessary to run the spanning tree protocol, bridges exchange special messages called configuration bridge protocol data unit (BPDU) messages. Conventional BPDU messages contain a number of fields, including a root identifier field, a root path cost field, a bridge identifier field and a port identifier field, among others. Each bridge initially assumes itself to the be the root and transmits BPDU messages accordingly. Upon receipt of a BPDU message, its contents are examined and compared with similar information (e.g., assumed root and lowest root path cost) stored by the receiving bridge. If the information from the received BPDU is xe2x80x9cbetterxe2x80x9d than the stored information, the bridge adopts the better information and uses it in the BPDUs that it sends from its ports, other than the port on which the xe2x80x9cbetterxe2x80x9d information was received. Although BPDU messages are not forwarded by bridges, the identifier of the root is eventually propagated to and adopted by all bridges as described above, allowing them to select their root ports and any designated port(s).
In response to network changes or failures, BPDU information is up-dated and/or times-out, causing the active topology to be re-calculated. As a result, ports may transition from the blocking state to the forwarding state and vice versa. That is, as a result of new BPDU information, a previously blocked port may learn that it should be in the forwarding state (e.g., it is now the root port or a designated port). Rather than transition directly from the blocking state to the forwarding state, ports typically transition through two intermediate states: a listening state and a learning state. In the listening state, a port waits for information indicating that it should return to the blocking state. If, by the end of a preset time, no such information is received, the port transitions to the learning state. At the end of a second preset time, the port transitions from the learning state to the forwarding state, thereby allowing data frames to be forwarded to and from the port.
Virtual Local Area Networks
A computer network may also be segregated into a series of logical network segments. For example, U.S. Pat. No. 5,394,402, issued on Feb. 28, 1995 to Ross (the xe2x80x9c""402 Patentxe2x80x9d), which is hereby incorporated by referenced in its entirety, discloses an arrangement for associating any port of a switch with any particular segregated network group. Specifically, according to the ""402 Patent, any number of physical ports of a particular switch may be associated with any number of groups within the switch by using a virtual local area network (VLAN) arrangement that virtually associates the port with a particular VLAN designation. More specifically, Ross discloses a switch or hub that associates VLAN designations with at least one local port and further associates those VLAN designations with messages transmitted from any of the ports to which the VLAN designation has been assigned.
The VLAN designation for each local port is stored in a memory portion of the switch such that every time a message is received by the switch on a local port the VLAN designation of that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in the memory portion based on the local port where the message originated. In addition to the ""402 patent, the IEEE has issued a standard for Virtual Bridged Local Area Networks. See IEEE Standard 802.1Q.
In many cases, it may be desirable to interconnect a plurality of these switches in order to extend the VLAN associations of ports in the network. Ross, in fact, states that an objective of his VLAN arrangement is to allow all ports and entities of the network having the same VLAN designation to interchange messages by associating a VLAN designation with each message. Thus, those entities having the same VLAN designation function as if they are all part of the same LAN. Message exchanges between parts of the network having different VLAN designations are specifically prevented in order to preserve the boundaries of each VLAN segment. For convenience, each VLAN designation is often associated with a different color, such as red, blue, green, etc.
GARP VLAN Registration Protocol
To disseminate information across computer networks, the IEEE developed the Generic Attribute Registration Protocol (GARP). GARP allows participants to make and withdraw declarations for a particular attribute. In response to a GARP declaration, other network participants register the parameter value(s) of the specified attribute at the port on which the declaration was received. GARP participants also propagate declarations so that other participants in the network can make the appropriate registrations. Participants can also withdraw their previous declarations. In response to a withdrawal, the other participants de-register the particular parameter value(s).
A GARP participant consists of a GARP application component and a GARP Information Declaration (GID) component. The GID component consists of a set of state machines that define the current registration and declaration state for all attribute values. A GARP participant is typically established for each port per GARP application. Thus, for intermediate devices, which often have multiple ports, multiple GARP participants are established. To make or withdraw declarations, GARP participants generate and send special messages called GARP Protocol Data Unit (GARP-PDU) messages. FIG. 1 is a block diagram of a conventional GARP-PDU message 100. The GARP-PDU message 100 typically includes a Media Access Control (MAC) header 102 that includes destination and source address fields, among other information, a protocol identifier (ID) field 104, a plurality of message fields, such as message fields 106, 108 and 110, and an end mark field 112. Each message field, moreover, includes an attribute type field 114 and an attribute list field 116. The attribute list field 116, in turn, includes one or more attribute fields, such as attribute fields 118, 120 and 122, and an end mark field 124. Each attribute field, such as field 118, includes an attribute length field 126, an attribute event field 128 and an attribute value field 130.
In order to exchange information among the GARP participants of a given intermediate device, a separate component, called the GARP Information Propagation (GIP) component, is used. The GIP component operates over a GIP context that is established at the intermediate device and defines the ports that are to be included in the given context. That is, although registration can occur at any port, the propagation of that registration only follows the associated GIP context. For example, a particular GIP context may consist of the ports that belong to the active topology (i.e., all ports in the forwarding state). Because blocked ports are not part of the GIP context, a declaration received on a blocked port is not propagated to any other ports, although it is still registered at the blocked port. In contrast, a declaration received at a forwarding port, which is part of the GIP context, is both registered at that port and propagated throughout the GIP context (i.e., to all of the other forwarding ports).
One application of GARP is to propagate VLAN designations across computer networks. More specifically, the IEEE also defined the GARP VLAN Registration Protocol (GVRP) through which intermediate devices and end stations can issue and revoke declarations regarding their membership in specific VLANs. See IEEE 802.1Q standard. Thus, GVRP provides a mechanism for end stations to ensure that they receive messages from other VLAN members, regardless of where in the network those other members may be located. For example, an end station that is assigned to the xe2x80x9cbluexe2x80x9d VLAN typically generates and sends a GARP-PDU message 100 containing the VLAN identifier (VID) for the xe2x80x9cbluexe2x80x9d VLAN designation in the attribute value field 130 and a registration request in the corresponding attribute event field 128. The GARP-PDU message 100 is then received at an intermediate device coupled to the end station. The intermediate device registers the xe2x80x9cbluexe2x80x9d VLAN at the port on which the GARP-PDU is received and, assuming the receiving port is in the forwarding state, also propagates the information for registration and forwarding from its other forwarding ports. The GARP-PDU from the end station is thus propagated across the network along the active topology defined by the spanning tree protocol. If tjie GARP-PDU is received by an intermediate device at a blocked port, the VLAN designation is merely registered at that blocked port. The VLAN designation is neither registered at the device""s other ports nor is it propagated by the device.
For computer networks defining a single spanning tree or active topology, the GVRP protocol provides an effective mechanism for disseminating VLAN membership information. Indeed, in the 802.1Q standard, the IEEE specifically calls for a single spanning tree or active topology to be defined for the entire bridged network including all VLAN designations. As an alternative to the 802.1Q standard, certain intermediate devices define a separate spanning tree for each VLAN designation. See Cisco Internetwork Operating System (IOS(copyright)) VLAN Services document. With this approach, a single port may be forwarding for one VLAN (e.g., xe2x80x9cbluexe2x80x9d), but blocking for a second VLAN (e.g., xe2x80x9credxe2x80x9d). Thus, messages associated with the xe2x80x9cbluexe2x80x9d VLAN designation are received and forwarded from the port, whereas messages associated with the xe2x80x9credxe2x80x9d VLAN designation are not. For interoperability with network segments defining a single spanning tree devices, these devices may also define a base or common spanning tree that is mapped to the single spanning tree in the network segments that operate single spanning trees. With multiple spanning trees, however, the conventional GVRP implementation cannot guarantee that VLAN membership information will be fully distributed throughout the network. That is, connectivity problems can occur.
In particular, with the conventional GVRP implementation, a single GIP context corresponding to the base spanning tree would be established. If a GVRP declaration requesting registration of the xe2x80x9cbluexe2x80x9d VLAN designation is received at a first intermediate device port that is in the forwarding state for xe2x80x9cbluexe2x80x9d VLAN, but in the blocking state for the base spanning tree, the registration would not be propagated from the first port. That is, because the first port is in the blocking state for the base spanning tree, it is not part of the GIP context. If the first port nonetheless represents the only path to certain members of the xe2x80x9cbluexe2x80x9d VLAN, none of the other blue VLAN members will learn of their existence. As a result, connectivity may be lost to the blue VLAN members xe2x80x9cbehindxe2x80x9d the first port. Accordingly, a need exists for ensuring that VLAN membership information is disseminated across and registered by computer networks running multiple spanning trees.
It is an object of the present invention to provide a method and apparatus for disseminating Virtual Local Area Network (VLAN) membership information across computer networks running multiple spanning trees.
It is a further object of the present invention to provide a method and apparatus for disseminating VLAN membership information across computer networks running multiple spanning trees that is also interoperable with network segments running one spanning tree or a plurality of shared spanning trees.
Briefly, the invention relates to a method and apparatus for disseminating Virtual Local Area Network (VLAN) membership information across computer networks running multiple spanning trees. In particular, an intermediate device includes a plurality of ports for interconnecting entities of a computer network. The device further includes a separate spanning tree engine for each instance of the spanning tree protocol running at the device. The spanning tree engines transition the ports of the device among a plurality of spanning tree states, including a forwarding state and a blocking state, per instance of the spanning tree protocol. For each port, a separate Generic Attribute Registration Protocol (GARP) paticipant is also established. Each GARP participant includes a multiple spanning tree (MST) GARP VLAN Registration Protocol (MST-GVRP) application component and an associated GARP Information Declaration (GID) component. The MST-GVRP application components cooperate to define a plurality of GARP Information Propagation (GIP) contexts each of which is associated with one of the instances of the spanning tree protocol. The multiple GIP contexts are then used to exchange VLAN membership information between the MST-GVRP application components and to disseminate that information across the network, thereby ensuring connectivity among all VLANs.
More specifically, for a given port, the MST-GVRP application component preferably queries the spanning tree engines to determine for which instances of the spanning tree protocol, if any, the given port is in the forwarding state. The MST-GVRP application component then joins as a participant in each of the GIP contexts for those instances of the spanning tree protocol for which its port is in the forwarding state. The MST-GVRP application component does not participate in those GIP contexts corresponding to the instances of the spanning tree protocol for which its port is in the blocking state. When a declaration requesting membership in a first VLAN is received at the MST-GVRP application component, it registers the declared VLAN designation at its port. Furthermore, if the port is in the forwarding state for the instance of the spanning tree protocol that corresponds to the declared VLAN designation (and thus participates in the corresponding GIP context), the MST-GVRP application component also distributes the declaration to the other ports participating in that GIP context. If the port is in the blocking state for the instance of the spanning tree protocol corresponding to the declared VLAN, the MST-GVRP application component merely registers the declared VLAN. It does not disseminate the declaration to any other ports.